# 面试题 02.07. 链表相交
# 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null
# 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
# 输出：Intersected at '8'
# 解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
# 从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
# 在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
#

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        la = lb = 0
        cura = headA
        curb = headB
        while cura != None:
            la += 1
            cura = cura.next
        while curb != None:
            lb += 1
            curb = curb.next
        if la > lb:
            cnt = la - lb
            while cnt:
                headA = headA.next
                cnt -= 1
        else:
            cnt = lb - la
            while cnt:
                headB = headB.next
                cnt -= 1
        while headA:
            if headA == headB:
                return headA
            else:
                headA = headA.next
                headB = headB.next
        return None


if __name__ == '__main__':
    # a = ListNode(1)
    # b = ListNode(2)
    # c = ListNode(3)
    # d = ListNode(4)
    # e = ListNode(3)
    # a.next = b
    # b.next = c
    # c.next = d
    # d.next = e
    pass
    # 我看了一下随想录上python的解法，骚气的一匹

